While the worst-case $O(n)$ performance of Linear Search requires checking every element, we can achieve vastly superior performance if the input data is sorted. This is the key prerequisite for the Binary Search algorithm.
- Binary Search works by targeting the middle element of the array $A$ (the pivot) and comparing it to the target $t$. Since the array is sorted, this single comparison allows us to eliminate half of the remaining data set immediately.
- Initialize low and high pointers to define the search space (initially $0$ and $n-1$).
- Calculate the midpoint index.
- Compare $A[\text{mid}]$ with $t$.
- Adjust either the low pointer (if $t$ is in the right half) or the high pointer (if $t$ is in the left half).
- The process repeats until the element is found or low crosses high (meaning the element is not present).
- This iterative elimination of half the search space is what drives Binary Search's tremendous efficiency, ultimately yielding a performance guarantee of $O(\log_2(n))$.
Algorithm Properties
| Property | Binary Search | Linear Search |
|---|---|---|
| Data Prerequisite | Sorted | Unsorted |
| Worst Case | $O(\log n)$ | $O(n)$ |
| Best Case | $O(1)$ | $O(1)$ |
| Average Case | $O(\log n)$ | $O(n)$ |